Internet Info 1994 March/Internet Info CD-ROM (Walnut Creek) (March 1994).iso/inet/internet-drafts/draft-rekhter-direct-provider-00.txt

Text File | 1993-10-26 | 19KB | 506 lines

                           - 1 -



Network Working Group                                      Y. Rekhter
INTERNET DRAFT                  T.J. Watson Research Center, IBM Corp.
<draft-rekhter-direct-provider-00.txt>                   October 1993


                      Selecting a Direct Provider


Status of this Memo


   This document is an Internet Draft.  Internet Drafts are working
   documents of the Internet Engineering Task Force (IETF), its Areas,
   and its Working Groups.  Note that other groups may also distribute
   working documents as Internet Drafts.

   Internet Drafts are draft documents valid for a maximum of six
   months.  Internet Drafts may be updated, replaced, or obsoleted by
   other documents at any time.  It is not appropriate to use Internet
   Drafts as reference material or to cite them other than as a
   ``working draft'' or ``work in progress.''

   Please check the 1id-abstracts.txt listing contained in the
   internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net,
   nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the
   current status of any Internet Draft.



1 Introduction


   Within the existing Internet routing architecture/protocols different
   hosts within a domain (autonomous system) usually can't control the
   choice of adjacent domains for forwarding of the inter-domain traffic
   originated by the hosts. In this document we describe a simple
   mechanism that provides hosts with such control. The proposed scheme
   can be realised with the existing technology, off-the shelf
   components, and minor tweaking of forwarding algorithm by border
   routers. The scheme doesn't require any new routing protocols.










Expiration Date April 1994                                      [Page 1]

                           - 2 -



2 Background


   The Internet is viewed as a set of arbitrary interconnected
   Autonomous Systems (Domains). An autonomous system that carries
   transit traffic is called a service provider (or just a provider). An
   autonomous system that uses other autonomous system(s) to carry
   locally originated traffic is called a service subscriber (or just a
   subscriber). A provider that has an external neighbor (in the
   BGP/IDRP sense) with one of the BGP/IDRP speakers within a subscriber
   is called the direct provider (with respect to the subscriber).  All
   other providers are called indirect (with respect to the subscriber).
   Routers that participate in inter-domain routing are called Border
   Routers or Border Intermediate Systems (BISs).

   Within the current Internet routing the choice of routes available to
   a host within a subscriber is limited to the routes selected by the
   BISs within the subscriber. Consequently, a route available from a
   direct provider, but not selected by the BISs within the subscriber
   can't be made available to a host within the subscriber.

   As an illustration of this limitation consider the following
   topology:


                  H1      B
                   \     / \
                    \   /   \
                     \ /     \
                      D       A
                     / \      /
                    /   \    /
                   /     \  /
                  /       \/
                 H2      C


   where A is a BIS that belong to domain RD-A, B is a BIS that belongs
   to domain RD-B, C is a BIS that belongs to domain RD-C, and D is a
   BIS that belongs to domain RD-D. H1 and H2 are two hosts in RD-D. D
   has to select between B and C as the next hop domain (BIS) to
   destinations in RD-A. Consequently, hosts within RD-D, H1 and H2,
   would be bounded by the D's choices. If H1 would prefer to use route
   to destinations in RD-A going through B, and H2 would prefer to use
   route to destinations in RD-A going through C, then superficially one





Expiration Date April 1994                                      [Page 2]

                           - 3 -



   would conclude that such route selection can't be satisfied within
   the current Internet routing. The following shows that such a
   conclusion is incorrect.



3 Solving the problem


   The problem of removing the limit of choices imposed on hosts within
   a subscriber by subscriber's BISs can be decomposed into three
   orthogonal, but somewhat related subproblems:


       - how a BIS within a subscriber that is connected to a particular
         direct provider learns about routes offered by the provider

       - how a router within a subscriber discovers a BIS that is
         connected to a particular direct provider - how to find a
         correct exit BIS

       - how to ensure forwarding within the subscriber that is
         consistent with the host's preference of the direct provider

   This document assumes that each provider has a globally unambiguous
   identifier that can be used both for the purpose of distributing
   routing information and for the purpose of packet forwarding.
   Furthermore, the document assumes that the autonomous system number
   (AS number) is used as such an identifier.


3.1 How a BIS discovers routes offered by a direct provider


   With BGP/IDRP ([1], [2]) a BIS stores the routes received from an
   external neighbor in the Adj-RIB-In (adjacency Routing Information
   Base input) associated with the neighbor.  For each external neighbor
   the BIS also knows the AS number of the provider the neighbor is in.
   Therefore, for each direct provider that has an external neighbor
   with a BIS, the BIS has sufficient information about the routes
   offered by the provider, as well as the provider's identifier (AS
   number).








Expiration Date April 1994                                      [Page 3]

                           - 4 -



3.2 How to find a correct exit BIS


   A BIS that is connected to a particular provider needs to pass the
   information about this connectivity to other BISs within its domain.
   This is accomplished by generating and propagating (via BGP/IDRP) to
   all of the BIS's internal neighbors (in BGP/IDRP sense) a route whose
   AS-PATH (RD-PATH) path attribute contains only the AS number of the
   provider and whose NLRI may be either empty or embeds the AS number.
   The choice of empty NLRI is determined by a particular routing
   protocol (whether the protocol allows to carry AS-PATH (RD-PATH), but
   no NLRI).  Since this route is distributed to all the BISs within the
   subscriber, any BIS within the subscriber can identify a BIS that has
   an external neighbor within a particular direct provider.

   The situation is a bit more complex for routers within the subscriber
   that are not BISs (they don't participate in BGP/IDRP). We suggest
   two possible schemes.

      Option 1:

         The first option requires the BIS that has an external neighbor
         with a particular provider to generate an intra-domain route to
         a destination that unambiguously identifies the AS number of
         the provider.  The Network Layer Reachability Information
         (NLRI) of such a route can be constructed by by embedding the
         AS number in an IP address.

      Option 2:

         The second option assumes that routers within a subscriber that
         don't participate in BGP/IDRP have a default route pointing to
         particular BISs (this default route may be either static or
         dynamic). Such a route would result in forwarding a packet
         whose destination is outside the subscriber to one of the BISs
         within the subscriber. Once the packet reaches the BIS, the BIS
         determines an appropriate exit BIS using information received
         via BGP/IDRP.


   To provide correct operations it is essential that there be a
   consistent scheme for embedding AS numbers into IP addresses.  A
   possible scheme for doing this is suggested in SDRP [3], where an AS
   number is embedded in the lower two octets of the 128.0.0.0 IP
   network number. For example, AS number 233 is encoded as 128.0.0.233.





Expiration Date April 1994                                      [Page 4]

                           - 5 -



3.3 How to provide consistent forwarding


   Providing forwarding that takes into account direct provider
   preferences requires an additional mechanism. This is because routes
   selected by BISs within a subscriber may not be consistent with the
   preferences of a particular host within the subscriber. The mechanism
   should be able to identify the host's preference for the purpose of
   packet forwarding.

   In this document we assume that a packet may carry certain explicit
   information that identifies a particular provider.  In general, this
   information can be carried as either an IP option or via an
   encapsulation.  This document assumes the use of encapsulation, such
   as SDRP [3] or GRE [4].

   When a host originates a packet, and the host has a certain
   preference with respect to a particular direct provider, the host
   needs to indicate this preference.  The host can indicate it either
   by itself or by relying on some proxy agent (e.g. first hop router).
   To indicate the preference for a particular direct provider the
   packet is encapsulated (by either the originating host, or by its
   proxy agent) and the destination address in the outer header embeds
   the AS number of the provider.

   If the information about direct providers is distributed via intra-
   domain routing (Option 1 in Section 3.2), then the packet will be
   forwarded via intra-domain routing procedures to the correct exit
   BIS.  The exit BIS will use the destination address in the outer
   header to determine the direct provider. The BIS then will
   decapsulate the packet and will use the destination address in the
   inner header of the packet to determine whether the Adj-RIB-In
   associated with the provider has a route to the destination specified
   in the original packet. If such a route exists, then the BIS will
   forward the packet to the neighbor associated with the Adj-RIB-In.
   Otherwise, the original packet will be forwarded using BIS's FIB
   (using normal forwarding procedures). The BIS may generate an ICMP
   Destination Unreachable message back to the entity that performed the
   encapsulation ( either the host that originated the packet, or its
   proxy agent) to indicate that the route through the provider desired
   by the host is unavailable.

   If the information about direct providers is not distributed via
   intra-domain routing (Option 2 in Section 3.2), then the packet will
   be forwarded via a default route to one of the BISs within the





Expiration Date April 1994                                      [Page 5]

                           - 6 -



   subscriber.  If that BIS happen to be a correct exit BIS (the BIS
   peers with an external neighbor, such that the neighbor belongs to
   the provider indicated by the packet), then the BIS will operate as
   described in the previous paragraph. Otherwise, the packet will be
   encapsulated one more time with the destination address in the outer
   header indicating the correct exit BIS. Once the packet reaches the
   correct exit BIS, the outer header will be stripped and the remaining
   processing will be performed precisely as described in the previous
   paragraph.

   This document assumes that within a subscriber that offers support
   for direct provider selection all the BISs trap packets whose
   destination indicates embedded provider identifier (AS number) and
   decapsulate these packets before forwarding them to external
   neighbors.

   If a BIS receives a packet whose destination indicates embedded
   provider identifier, and the BIS determines that the provider is not
   a direct provider of the subscriber the BIS is in, the BIS should
   generate an ICMP Destination Unreachable message to the entity that
   performed the encapsulation (either the host that originated the
   packet or some proxy agent acting on behalf of the host).  The entity
   should use this message as an indication that the selected provider
   is unavailable.

   A host  (or its proxy agent) is not required to maintain information
   about all the direct providers of the subscriber the host is in. If a
   host (or its proxy agent) specifies a provider that is not a direct
   provider of the subscriber, then packets originated by the host (or
   its proxy agent) will be forwarded based on the choices of the direct
   provider made by the BISs within the subscriber.

   When a host (or its proxy agent) receives an ICMP Destination
   Unreachable message indicating unavailability of the route through a
   particular provider, the host (or its proxy agent) should either
   change its selected provider or should stop using direct provider
   selection mechanism altogether.


3.4 An example of operations


   We illustrate how the proposed scheme operates using the topology
   described in Section 2. Assume that D prefers routes through B to
   destinations in A, but when connectivity to B fails or B doesn't have





Expiration Date April 1994                                      [Page 6]

                           - 7 -



   routes to destinations in A, D would switch to routes through C. The
   routes selected by D are consistent with H1's choices for the direct
   provider (use B as a primary, use C as a fallback), but are in
   conflict with H2's choices for the direct provider (use C as a
   primary, use B as a fallback). To satisfy H2's preferences for the
   direct provider, H2 encapsulates its outgoing packets, such that the
   destination address in the outer header embeds C's AS number.  When
   such a packet reaches D, D uses the destination address to identify
   the Adj-RIB-In associated with C, performs decapsulation, and then
   checks whether the Adj-RIB-In has a route to the destination
   specified in the inner header.  If such a route exists, then the
   packet is forwarded to C.  Otherwise, the packet is forwarded using
   D's FIB, which results in forwarding the packet to B.

   If the connectivity between C and A is present, then D will forward
   the packets originated by H2 through C. When the connectivity is
   disrupted the D's Adj-RIB-In that is associated with C will not have
   a route to destinations in A, so D will forward the packets through
   B. In this case D will generate an ICMP Destination Unreachable
   message back to H2. H2 is expected to use this message as an
   indication that route through the selected provider is unavailable.

   To illustrate how the proposed scheme operates when a host selects a
   provider who is not a direct provider of the subscriber the host is
   in, assume that H2 selects X as its direct provider.  In this case H2
   will receive an ICMP Destination Unreachable message either from a
   BIS or from some other router within the subscriber, and should use
   this message as an indication that no route through the selected
   provider (X) is available.


4 Multiple preferences


   A host (or its proxy agent) may have preferences for more than one
   direct provider. The list of such preferences may be either ordered
   (first try direct provider X, if that is impossible then try direct
   provider Y, etc...), or unordered (try a direct provider X, but if
   not available pick at random another provider from the list).  The
   proposed scheme doesn't allow to simultaneously specify multiple
   choices for direct providers. That is, a packet contains identity of
   only one preferred provider. The host (or its proxy agent) relies on
   the ICMP Destination Unreachable messages to determine the
   feasibility of using the direct provider selected by the host.






Expiration Date April 1994                                      [Page 7]

                           - 8 -



5 Limitations


   The proposed scheme supports only a "soft" selection. That is, if a
   route through a selected provider isn't available, or the selected
   provider is not a direct provider of the subscriber the host is in,
   the subscriber will use its selected direct provider.

   This proposal doesn't distinguish between the case where a host
   selects a provider who is not a direct provider of the subscriber the
   host is in, and the case where a host selects a direct provider, but
   there is no route through that provider.

   While the proposed solution may be suitable to solve other problems,
   such a discussion is outside the scope of this document.
   Specifically, suitability of the proposed solution to an arbitrary
   policy-based routing problem (a.k.a. "arbitrary internet" (AI)
   problem) is outside the scope of this document.


6 Conclusions


   This document describes how the existing routing protocols combined
   with encapsulation and minor changes to forwarding algorithm can be
   used to solve the problem of direct provider selection.  It provides
   the same dynamic rerouting capabilities as available with the
   existing routing architecture/protocols.  The scheme doesn't require
   introduction of any new routing protocols and/or new network layer
   protocol - it is based pretty much on existing off-the-shelf
   components.

   The functionality provided by the scheme described in the document is
   quite similar to the "long-distance" provider selection available in
   today's telephony, where a caller (host) can either use the long-
   distance carrier (direct provider) selected by the RBOC the caller is
   attached to, or may explicitly indicate its preference for a
   particular long long-distance carrier.  The scheme may be used in
   similar circumstances to enable "long-distance" provider selection
   functionality in the Internet.

   While the scheme is described in terms of IP, it can be directly
   applicable to other existing connectionless network layer protocols,
   like CLNP.






Expiration Date April 1994                                      [Page 8]

                           - 9 -



6 Acknowledgements


   This proposal was largely stimulated by discussions with Robert
   Brenner (GTE) and Peter Ford (LANL).

   The author would like to express his deep thanks and appreciation to
   Susan Hares (MERIT), Tony Li (cisco Systems), and Jessica Yu (MERIT)
   for their review and constructive comments.


References

   [1] Rekhter, Y., Li, T., `A Border Gateway Protocol 4 (BGP-4)',
   Internet Draft, April 1993

   [2] Hares, S., `IDRP for IP', Internet Draft, March 1993

   [3] Estrin, D., Zappala, D., Li, T., Rekhter, Y., "Source Demand
   Routing: Packet Format and Forwarding Specification (Version 1)"
   Internet Draft, September 1993

   [4] Hanks, S., Li, T., Farinacci, D., Traina, P., "Generic Routing
   Encapsulation (GRE)", Internet Draft, September 1993


Security Considerations

   Security issues are not discussed in this memo.


Author's Addresses

   Yakov Rekhter
   T.J. Watson Research Center IBM Corporation
   P.O. Box 218
   Yorktown Heights, NY 10598
   Phone:  [phone]
   email:  [e-mail]











Expiration Date April 1994                                      [Page 9]